﻿// Cheapest Palindrome POJ - 3280 训练营.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://vjudge.net/problem/POJ-3280#author=GPT_zh

跟踪所有奶牛可能是一项棘手的任务，因此农夫约翰安装了一个系统来自动化这个过程。他在每头奶牛上都安装了一个电子ID标签，当奶牛经过扫描器时，系统会读取这个标签。每个ID标签的内容目前是一个长度为M（1 ≤ M ≤ 2,000）的字符串，由N（1 ≤ N ≤ 26）个不同的符号（即，小写罗马字母）组成。

奶牛们，作为顽皮的生物，有时会尝试通过倒着走来欺骗系统。虽然一个ID为"abcba"的奶牛无论她走的方向如何，读取的都是相同的，但是一个ID为"abcb"的奶牛可能会注册为两个不同的ID（"abcb"和"bcba"）。

FJ希望改变奶牛的ID标签，使得无论奶牛走的方向如何，读取的都是相同的。例如，"abcb"可以通过在末尾添加"a"来改变为"abcba"，使得ID是回文的（正向和反向读取都是相同的）。其他改变ID为回文的方法包括在开头添加三个字母"bcb"来得到ID"bcbabcb"，或者删除字母"a"来得到ID"bcb"。可以在字符串的任何位置添加或删除字符，得到的字符串可能比原来的字符串长或短。

不幸的是，由于ID标签是电子的，每个字符的插入或删除都有一个成本（0 ≤ cost ≤ 10,000），这个成本取决于要添加或删除的字符的具体值。给定一头奶牛的ID标签的内容和插入或删除字母表中每个字符的成本，找出改变ID标签以满足FJ要求的最小成本。一个空的ID标签被认为满足正向和反向读取相同的要求。只有与成本相关的字母可以添加到字符串中。

输入
第1行：两个空格分隔的整数：N和M
第2行：这一行包含恰好M个字符，构成了初始的ID字符串
第3行到第N+2行：每行包含三个空格分隔的实体：输入字母表的一个字符和两个整数，分别是添加和删除该字符的成本。
输出
第1行：一个单独的行，包含一个整数，表示改变给定名牌的最小成本。

3 4
abcb
a 1000 1100
b 350 700
c 200 800

900

如果我们在末尾插入一个"a"得到"abcba"，成本将是1000。如果我们删除开头的"a"得到"bcb"，成本将是1100。如果我们在字符串的开头插入"bcb"，成本将是350 + 200 + 350 = 900，这是最小的。
*/
int main()
{
    std::cout << "Hello World!\n";
}
 